#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 1000001
#define NIL -1

typedef int Position;
typedef struct StringNode *String;
struct StringNode {
    char data[kMaxSize]; /* 存储字符的数组 */
    int length; /* 字符串长度 */
};

String InitStr() {
    /* 初始化一个空的字符串 */
    String s;

    s = (String)malloc(sizeof(struct StringNode));
    s->length = 0;

    return s;
}

/* 算法4-13：求解字符串t的next数组  GetNext (t, next) */
void GetNext(String t, int next[]) {
    int m, i, j;

    m = t->length;
    next[0] = -1;
    for (i = 1; i < m; i++) { /* 求出next[1]~next[m-1] */
        j = next[i - 1];
        while ((j >= 0) && (t->data[i] != t->data[j + 1])) {
            j = next[j];
        }
        if (t->data[i] == t->data[j + 1]) {
            next[i] = j + 1;
        } else {
            next[i] = -1;
        }
    }
}
/* 算法4-13 结束 */

/* 算法4-14：字符串匹配的KMP算法  PatternMatchKMP(s, t) */
Position PatternMatchKMP(String s, String t) {
    int n, m, i, j;
    Position p;
    int *next;

    n = s->length;
    m = t->length;
    p = NIL;
    if (n >= m) {
        next = (int *)malloc(sizeof(int) * m);
        GetNext(t, next); /* 计算next数组 */
        i = j = 0;
        while ((j < n) && (i < m)) {
            /* 若匹配成功则两指针同时向右移动 */
            if (s->data[j] == t->data[i]) {
                i++;
                j++;
            } else if (i > 0) { /* 失配且t指针未回退到左端 */
                i = next[i - 1] + 1; /* 计算t的匹配起始位置 */
            } else { /* 失配且t从头开始与s的下一段比较 */
                j++;
            }
        }
        if (i == m) { /* t完成了匹配 */
            p = j - m; /* 匹配成功的位置 */
        }
    }
    return p;
}
/* 算法4-14 结束 */

String ReadString() {
    int i;
    String s;

    s = InitStr(); /* 创建空的字符串 */
    i = 0;
    s->data[i] = getchar();
    while (s->data[i] != '\n') {
        i++;
        s->data[i] = getchar();
    }
    s->data[i] = '\0'; /* 字符串结束符占1位 */
    s->length = i;
    return s;
}

int main(void) {
    String s, t;
    Position p;

    s = ReadString();
    t = ReadString();
    p = PatternMatchKMP(s, t);
    if (p != NIL)
        printf("%s\n", s->data + p);
    else
        printf("匹配失败。\n");

    return 0;
}